#ifndef __BITMAP_H__
#define __BITMAP_H__
#include <assert.h>
#include <stdint.h>
#include <string.h>

extern uint8_t mask[8];
extern uint8_t on_list_map[256][8];
extern uint8_t on_num_map[256];
extern uint8_t off_list_map[256][8];
extern uint8_t off_num_map[256];

class BitMap
{
public:
	BitMap(int iBitNum)
	:m_iBitNum(iBitNum)
	,m_iOnBits(0)
	{
		if(m_iBitNum == 0)
		{
			m_iSize = m_iBitNum;
			m_pData = NULL;
			return;
		}
		m_iSize = ((m_iBitNum+7)&~7)/8;
		m_pData = new uint8_t[m_iSize];
		assert(m_pData);
	}
	~BitMap()
	{
		if(m_pData != NULL)
			delete[] m_pData;
	}

	//iIndex=[0,N]
	inline bool IsOn(int iIndex)
	{
		if(iIndex >= m_iBitNum || iIndex < 0)
			return false;
		
		return m_pData[iIndex/8] & mask[iIndex%8];
	}
	
	//iIndex=[0,N]
	inline bool On(int iIndex)
	{
		if(iIndex >= m_iBitNum || iIndex < 0)
			return false;

		if(!IsOn(iIndex))
		{
			m_pData[iIndex/8] |= mask[iIndex%8];
			m_iOnBits++;
		}
		return true;
	}

	//iIndex=[0,N]
	inline bool Off(int iIndex)
	{
		if(iIndex >= m_iBitNum || iIndex < 0)
			return false;
		
		if(IsOn(iIndex))
		{
			m_pData[iIndex/8] &= ~mask[iIndex%8];
			m_iOnBits--;
		}
		return true;
	}

	inline int OnNum()
	{
		return m_iOnBits;
	}

	//iBeginIdx=[N...]
	inline bool OffIndexs(int* pList, int iBeginIdx, int& iSize)
	{
		assert(pList);
		int k = 0;
		int n = 0;
		for(int i=iBeginIdx/8; i<m_iSize; i++)
		{
			if(m_pData[i] == 0xff) continue;

			const uint8_t* pIdxs = off_list_map[m_pData[i]];	
			for(int j=0; (j<off_num_map[m_pData[i]])&&(k<iSize); j++)
			{
				n = pIdxs[j]+i*8;
				if(n >= iBeginIdx)
				{
					pList[k++] = n;
				}
			}
		}
		return (iSize = k);
	}


	//iBeginIdx=[N...]
	inline bool OnIndexs(int* pList, int iBeginIdx, int& iSize)
	{
		assert(pList);
		int k = 0;
		int n = 0;
		for(int i=iBeginIdx/8; i<m_iSize; i++)
		{
			if(m_pData[i] == 0x00) continue;

			const uint8_t* pIdxs = on_list_map[m_pData[i]];	
			for(int j=0; (j<on_num_map[m_pData[i]])&&(k<iSize); j++)
			{
				n = pIdxs[j]+i*8;
				if(n >= iBeginIdx)
				{
					pList[k++] = n;
				}
			}
		}
		return (iSize = k);
	}

	inline void Reset()
	{
		memset(m_pData, 0x00, m_iSize);
		m_iOnBits = 0;
	}
private:
	uint8_t* m_pData;
	int m_iSize;
	int m_iBitNum;
	int m_iOnBits;
};

#endif

